/* 565. 数组嵌套 */
/**
 * @param {number[]} nums
 * @return {number}
 */

/* 

    图
    遍历数组,从i到nums[i]连边，我们可以得到一张有向图
    在不含有重复元素的情况下，有向图必然由一个或多个环组成，找到节点个数最大的环
*/
var arrayNesting = function (nums) {
	let ans = 0,
		n = nums.length
	const vis = new Array(n).fill(0)
	for (let i = 0; i < n; i++) {
		let cnt = 0
		while (!vis[i]) {
			vis[i] = true
			i = nums[i]
			++cnt
		}
		ans = Math.max(ans, cnt)
	}
	return ans
}
/* 
    原地标记
    利用[nums中元素的大小在[0,n-1]之间这一条件，我们可以省略vis数组]
 */
var arrayNesting = function (nums) {
	let ans = 0,
		n = nums.length
	for (let i = 0; i < n; ++i) {
		let cnt = 0
		while (nums[i] < n) {
			const num = nums[i]
			nums[i] = n
			i = num
			++cnt
		}
		ans = Math.max(ans, cnt)
	}
	return ans
}
const size = arrayNesting([5, 4, 0, 3, 1, 6, 2])
console.log('arrayNesting :>>', size)
